package algotithm.leetcode.dp.hot.test139;
/**
*@author zhouyanxiang
*@Date 2021-02-2021/2/9-22:09
*/
public class Solution {

    public static void main(String[] args) {

    }

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int ind = 0;
        int[] lower = new int[len];
        for (int i = 0; i < len; i++) {
            int point = lowerBound(lower,ind,nums[i]);
            lower[point] = nums[i];
            if (point == ind) {
                ind++;
            }
        }
        return ind;
    }
    public static int lowerBound(int[] lower, int len, int num) {
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (lower[mid] < num) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}
